import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class T5LongestPalindrome {
    /**
     *5. 最长回文子串
     * 给你一个字符串 s，找到 s 中最长的回文子串。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "babad"
     * 输出："bab"
     * 解释："aba" 同样是符合题意的答案。
     * 示例 2：
     *
     * 输入：s = "cbbd"
     * 输出："bb"
     * 示例 3：
     *
     * 输入：s = "a"
     * 输出："a"
     * 示例 4：
     *
     * 输入：s = "ac"
     * 输出："a"
     *
     *
     * 提示：
     *
     * 1 <= s.length <= 1000
     * s 仅由数字和英文字母（大写和/或小写）组成
     * 题目地址:
     * https://leetcode-cn.com/problems/longest-palindromic-substring/
     *
     * 解题思路：
     * 从0开始，逐个做回文比较，将奇偶两种情况合并在一起进行，每次步进0.5。核心为中心扩展法
     */
    public String longestPalindrome(String s) {
        if(s==null||s.length()==0){
            return "";
        }
        int n=s.length();
        char[] chars=s.toCharArray();
        float maxPos=-1;
        int maxLen=-1;
        float middle=0;
        while (middle<=n-1){
            int i=0;
            int roundCount=0;
            while (middle+i<=n-1&&middle-i>=0){
                int offset=Math.ceil(middle)!=Math.floor(middle)?0:1;
                int iL=new Double(Math.floor(middle)).intValue()-i;
                int iR=new Double(Math.ceil(middle)).intValue()+i;
                if(chars[iL]==chars[iR]){
                    roundCount++;
                    if(roundCount>0&&roundCount*2-offset>maxLen){
                        maxLen=roundCount*2-offset;
                        maxPos=middle;
                    }
                }else{
                    break;
                }
                i++;
            }

            middle+=0.5;
        }
        int offset= Math.ceil(maxPos)==Math.floor(maxPos)?1:0;
        int iL= (int) (Math.ceil(maxPos)-(maxLen-offset)/2);
        System.out.println(maxPos+","+maxLen);
        return s.substring(iL,iL+maxLen);
    }

    public static void main(String[] args) {
        T5LongestPalindrome t5=new T5LongestPalindrome();
        System.out.println(t5.longestPalindrome("ytiihugyutyrygbabccbad"));
    }
}
